package com.ycz.algorithm.utils.hash;

/**
 * @author yancz
 * @ClassName HashMapOpenAddressing
 * @description: 开放寻址哈希表的实现
 * @date 2024-12-05 17:55:08
 * @version: 1.0
 */
public class HashMapOpenAddressing {

    private int size; // 键值对数量

    private int capacity = 4; // 哈希表容量

    private final double loadThres = 2.0 / 3.0; // 触发扩容的负载因子阈值

    private int extendRatio = 2; // 扩容倍数

    private Pair[] buckets; // 桶数组

    private final Pair TOMBSTONE = new Pair(-1, "-1"); // 删除标记

    // 哈希表初始化
    public HashMapOpenAddressing() {
        size = 0;
        buckets = new Pair[capacity];
    }

    // 哈希函数
    public int hashFunction(int key) {
        return key % capacity;
    }

    // 计算负载因子，公式为键值对数量 / 哈希表的容量
    public double loadFactor() {
        return (double) size / capacity;
    }

    /*
     * @author yancz
     * @description 查找key对应的桶索引
     * @date 2024/12/17 15:39
     * @param key
     * @return int
     **/
    public int findBucket(int key) {
        int index = hashFunction(key);
        int firstTombstone = -1;
        // 线性探测，遇到空桶时跳出，桶不为空时，继续探测
        while (buckets[index] != null) {
            if (buckets[index].key == key) { // 如果该桶的元素的键等于目标key
                if (firstTombstone != -1) { // 如果之前遇到过删除标记
                    buckets[firstTombstone] = buckets[index]; // 将该元素移动到删除标记的位置，并将当前位置标记为删除
                    buckets[index] = TOMBSTONE;
                    return firstTombstone; // 返回删除标记的位置
                }
                return index; // 如果没有删除标记，直接返回当前桶索引
            }
            // 记录遇到的首个删除标记
            if (firstTombstone == -1 && buckets[index] == TOMBSTONE) {
                firstTombstone = index;
            }
            index = (index + 1) % capacity; // 如果没有找到，线性探测到下一个桶
        }
        return firstTombstone == -1 ? index : firstTombstone; // 如果没有找到该元素，返回插入点的桶索引
    }

    // 查询
    public String get(int key) {
        int index = findBucket(key);
        if (buckets[index] != null && buckets[index] != TOMBSTONE) { // 若桶元素不为空且没有删除标记
            return buckets[index].val;
        }
        return null;
    }

    // 添加
    public void put(int key, String val) {
        if (loadFactor() > loadThres) { // 负载因子超过阈值，哈希表扩容
            extend();
        }
        int index = findBucket(key); // 找到key对应的桶索引
        if (buckets[index] != null && buckets[index] != TOMBSTONE) {
            buckets[index].val = val;
            return;
        }
        // 键值对不存在，添加，并且容量+1
        buckets[index] = new Pair(key, val);
        size++;
    }

    // 删除
    public void remove(int key) {
        int index = findBucket(key);
        if (buckets[index] != null && buckets[index] != TOMBSTONE) {
            buckets[index] = TOMBSTONE; // 打上删除标记
            size--; // 容量-1
        }
    }

    // 哈希表扩容
    private void extend() {
        Pair[] bucketsTemp = buckets; // 暂存原哈希表
        capacity *= extendRatio;
        buckets = new Pair[capacity]; // 新哈希表
        size = 0;
        for (Pair pair : bucketsTemp) {
            if (pair != null && pair != TOMBSTONE) {
                put(pair.key, pair.val);
            }
        }
    }

    // 哈希表打印
    public void print() {
        System.out.println("哈希表容量：" + capacity);
        for (Pair pair : buckets) {
            if (pair == null) { // 元素为空
                System.out.println("null");
            } else if (pair == TOMBSTONE) { // 元素已删除
                System.out.println("该元素已删除");
            } else {
                System.out.println(pair.key + "===>" + pair.val);
            }
        }
    }

    public static void main(String[] args) {
        HashMapOpenAddressing hashMapOpenAddressing = new HashMapOpenAddressing();
        // 添加元素
        hashMapOpenAddressing.put(0, "a");
        hashMapOpenAddressing.put(1, "b");
        hashMapOpenAddressing.put(2, "c");
        hashMapOpenAddressing.print();
        System.out.println("-------------------------------");
        hashMapOpenAddressing.put(3, "e");
        hashMapOpenAddressing.put(4, "f");
        hashMapOpenAddressing.print();
        System.out.println("-------------------------------");
        // 查找元素
        System.out.println("key为3的键对应的值：" + hashMapOpenAddressing.get(3));
        System.out.println("key为5的键对应的值：" + hashMapOpenAddressing.get(5));
        System.out.println("-------------------------------");
        // 删除元素
        hashMapOpenAddressing.remove(3);
        hashMapOpenAddressing.print();
        System.out.println("-------------------------------");
        hashMapOpenAddressing.put(3, "e");
        hashMapOpenAddressing.print();
    }

}
